#include <iostream>
#include <string>
#include <memory.h>
using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {

        int len = s.size();
        if (numRows <= 1) {
            return s;
        }

        if(len <= numRows) {
            return s;
        }

        int row = numRows;
        int unit_span = 1 + row - 2;
        int unit = row + row - 2;
        int n = len/unit;
        int r = len%unit;

        int col = n*unit_span;
        int border;

        if (r == 0) {
        } else if (r <= row) {
            col += 1;
        } else {
            col += r - row;
        }
        border = col + 1;

        int pos = 0, idx=0;
        char *buf = (char *)malloc(row*border);
        for (int i=0;i<row;i++) {
            for (int j=0; j<border; j++) {
                buf[i*border+j] = ' ';
            }
        }
        for (int i=1;i<=row;i++) {
            buf[i*border-1]='\n';
        }
        while(idx < len) {

            for (int i=0; i<row && idx<len; i++) {
                buf[pos+border*i] = s[idx++];
            }
            for (int i=row-2; i>0 && idx<len; i--) {
                buf[pos+i*border+row-1-i] = s[idx++];
            }
            pos += unit_span;
        }

        string ret;
        ret.resize(len);
        for (int i=0, idx=0; i<row*border && idx<len; i++) {
            if (buf[i]!=' ' && buf[i]!='\n') {
                ret[idx++] = buf[i];
            }
        }
        free(buf);
        return ret;
    }
};


int main() {

//    string str = "PAYPALISHIRING";
    string str = "huangzhendong";
    Solution s;
    cout << s.convert(str, 2) << endl;
    cout << s.convert(str, 3) << endl;
    cout << s.convert(str, 4) << endl;
    cout << s.convert(str, 5) << endl;

}

